Compendium Deluxe 1

home *** CD-ROM | disk | FTP | other *** search

/ Compendium Deluxe 1 / LSD Compendium Deluxe 1.iso / a / programming / assembly / talinasm.lha / pmatch.asm < prev next >

Wrap

Assembly Source File | 1991-09-12 | 20.5 KB | 760 lines

* ======================================================================== * pmatch.asm -- routines to emulate AmigaDOS 2.0 pattern matcher * ©1991 by Talin / Sylvan Technical Arts * ======================================================================== ; register usage: ; d0 - scratch ; d1 - next opcode ; d2 - scratch ; d3 - IsWild ; d4 - stack limit ; d5 - 'all' flag ; a0 - scratch ; a1 - scratch ; a2 - pattern ; a3 - out ; a4 - outlimit ; a5 - start of opcode / save PMATCH_EOS equ $00 PMATCH_NULL equ $10 PMATCH_NOT equ $20 PMATCH_WILD equ $30 PMATCH_POUND equ $40 PMATCH_CLASS equ $50 PMATCH_NCLASS equ $60 PMATCH_STRING equ $70 PMATCH_CHOICE equ $80 PMATCH_SKIP equ $90 TICK equ 0x27 xref ToEnglish far code patch_zeroop: moveq #0,d0 ; op size = 0 patch_op: ; (a5 = loc, d1 = op, d0 = size ) move.b d0,1(a5) ; loc[1] = size; lsr.w #8,d0 ; size >>= 8 and.w #$0f,d0 ; size &= 0x0f or.w d1,d0 ; size += op move.b d0,(a5) ; loc[0] = size; rts opheader: move.l a3,d0 ; get output pointer addq.l #2,d0 ; add sizeof opcode sub.l a4,d0 ; subtract output limit bpl.s 1$ ; if over, then do nothing addq.w #2,a3 ; add sizeof opcode to output ptr 1$ rts ; return opdata: move.l a3,d2 ; get output pointer addq.l #1,d2 ; add sizeof byte sub.l a4,d2 ; subtract output limit bpl.s 1$ ; if over, then do nothing move.b d1,(a3)+ ; write data to output buffer 1$ rts ; return ppregs reg d2-d5/a2-a5 xdef _PatternParse,PatternParse _PatternParse movem.l ppregs,-(sp) ; save registers move.l 32+4(sp),a2 ; get pattern address move.l 32+8(sp),a3 ; output buffer address move.l 32+12(sp),d0 ; size of output buffer bra.s pp1 ; go to C entry point PatternParse: ; (a2 = pattern, a3 = output buffer, d0 = limit) movem.l ppregs,-(sp) ; save registers pp1: move.l a3,a4 ; a4 <-- output buffer add.l d0,a4 ; add size of buffer to get out limit moveq #0,d3 ; set IsWild to zero moveq #-1,d5 ; set ALL to TRUE move.l sp,d4 ; d4 <-- stack pointer sub.l #400,d4 ; d4 <-- lower limit of stack bsr parse_pattern ; call recursive routine beq.s 1$ ; if failed, return normally move.b (a2),d0 ; get last character looked at bne.s 2$ ; if not zero, then failed. move.l a3,d0 ; get output pointer addq.l #2,d0 ; add 2 sub.l a4,d0 ; subtract output limit bpl.s 2$ ; if over the end, then error moveq #0,d1 ; terminate buffer bsr opdata ; write out opcode bsr opdata ; and opdata move.l d3,d0 ; return IsWild movem.l (sp)+,ppregs ; restore registers rts ; return 2$ moveq #-1,d0 ; failed because of match error 1$ movem.l (sp)+,ppregs ; restore registers rts ; return ;---------- recursive pattern parsing subroutine parse_pattern: ;---------- save a5 on the stack, and check to make sure stack is not too deep move.l a5,-(sp) ; save starting point cmp.l sp,d4 ; compare stack ptr to stack limit bhs parse_fail ; if d4 is higher, then stack too deep *int parse_pattern(void) *{ ;---------- a pattern or sub-pattern cannot start with a termination character ; such as ')' or '|' * /* pattern or pattern substring can't start with closing delimiter */ * * if (*pat == '|' || *pat == ')') * { goto fail; * } move.b (a2),d0 ; d0 <-- current pattern character cmp.b #'|',d0 ; if '|' character (or) beq parse_fail ; goto fail cmp.b #')',d0 ; if close paren beq parse_fail ; goto fail ;---------- loop through the characters in the pattern, and take action based ; on the character seen. * while (*pat) * { char *start = out; * if (*pat == ')' || *pat == '|') return TRUE; loop1: move.b (a2),d0 ; d0 <-- *pat beq parse_succeed ; if character == '\0' then success move.l a3,a5 ; a5 <-- start of next output opcode cmp.b #'|',d0 ; if '|' character (or) beq parse_succeed ; end of pattern, pop a level cmp.b #')',d0 ; if close paren beq parse_succeed ; end of pattern, pop a level addq #1,a2 ; skip over character parsed ;---------- parse '#' (repeat) symbol * else if (*pat == '#') * { pat++; * opheader(); * unless (parse_pattern()) goto fail; * patch_op(PMATCH_POUND,start,out-start-2); cmp.b #'#',d0 ; if '#' character (repeat) bne.s 10$ ; then bsr opheader ; reserve space for op header move.w d5,-(sp) ; save ALL flag moveq #0,d5 ; ALL = false bsr parse_pattern ; call parse_pattern recursively move.w (sp)+,d5 ; restore ALL flag tst.w d0 ; return beq parse_fail ; if failed, then also fail 4$ moveq #PMATCH_POUND,d1 ; op = PMATCH_POUND 5$ move.l a3,d0 ; d0 <-- out sub.l a5,d0 ; d0 <-- out - start subq.l #2,d0 ; d0 <-- out - start - 2 (size of op) bsr patch_op ; patch in the opcode. moveq #1,d3 ; IsWild = 1 (wildcards present) bra loop1 ; next character ;---------- parse '*' (star) symbol * else if (*pat == '*') * { pat++; * opheader(); * opheader(); * patch_op(PMATCH_WILD,start+2,0); * patch_op(PMATCH_POUND,start,out-start-2); 10$ cmp.b #'*',d0 ; if '*' character (star) bne.s 20$ ; then bsr opheader ; reserve space for POUND op header bsr opheader ; reserve space for WILDCARD op header addq #2,a5 ; start += 2 moveq #PMATCH_WILD,d1 ; op = PMATCH_WILD bsr patch_zeroop ; patch op with no data field subq #2,a5 ; start -= 2 ; moveq #PMATCH_POUND,d1 ; op = PMATCH bra.s 4$ ; do nstd_patch ;---------- parse '~' (negate) symbol * else if (*pat == '~') * { pat++; * opheader(); * patch_op(PMATCH_NOT,start,0); 20$ cmp.b #'~',d0 ; if '~' character (negate) bne.s 30$ ; then moveq #PMATCH_NOT,d1 ; op = PMATCH_NOT bsr opheader ; reserve space for op header bsr patch_zeroop ; patch op with no data field moveq #1,d3 ; IsWild = 1 (wildcards present) bra.s loop1 ; get next character ;---------- parse '%' (null) symbol * else if (*pat == '%') * { pat++; * opheader(); * patch_op(PMATCH_NULL,start,0); 30$ cmp.b #'%',d0 ; if '%' character (null) bne.s 40$ ; then moveq #PMATCH_NULL,d1 ; op = PMATCH_NULL bra std_patch ; finish up op ;---------- parse '?' (wildcard) symbol * else if (*pat == '?') * { pat++; * opheader(); * patch_op(PMATCH_WILD,start,0); 40$ cmp.b #'?',d0 ; if '?' character (wildcard) bne.s 50$ ; then moveq #PMATCH_WILD,d1 ; op = PMATCH_WILD bra std_patch ; finish up op ;---------- parse '[' (class) symbol * else if (*pat == '[') 50$ cmp.b #'[',d0 ; if '[' character (class) bne.s 60$ ; then * { int op = PMATCH_CLASS; move.w #PMATCH_CLASS,-(sp) ; save PMATCH_CLASS on stack * pat++; * opheader(); bsr opheader ; reserve space for op header * if (*pat == '~') * { pat++; * op = PMATCH_NCLASS; * } cmp.b #'~',(a2) ; if it's a negative class bne.s 51$ ; then addq #1,a2 ; skip over that character move.w #PMATCH_NCLASS,(sp) ; store PMATCH_NCLASS on stack 51$: * for (;;) * { if (*pat == '\0') goto fail; * if (*pat == ']') break; * if (*pat == TICK) pat++; * opdata(ToEnglish(*pat++)); * } 52$ move.b (a2)+,d0 ; get next character beq.s 59$ ; if no closing bracket, fail cmp.b #']',d0 ; if it's a closing bracket beq.s 58$ ; then exit the loop cmp.b #TICK,d0 ; if it's a tick mark bne.s 55$ ; then move.b (a2)+,d0 ; bump pointer 55$ jsr ToEnglish ; convert to english move.w d0,d1 ; to d1 bsr opdata ; write it out bra.s 52$ ; next character in char class * if (*pat != ']') return FALSE; (not needed now) * pat++; * patch_op(op,start,out-start-2); 58$ move.w (sp)+,d1 ; d1 <-- PMATCH_(N)CLASS bra 5$ ; do nstd_patch 59$ addq #2,sp ; clean up stack bra parse_fail ; return failure ;---------- parse '(' (group) symbol * else if (*pat == '(') 60$ cmp.b #'(',d0 ; if '(' character (group) bne 70$ ; then * { UBYTE *last_goto = NULL; * pat++; clr.l -(sp) ; push last_goto on stack (zero now) move.b (a2),d0 ; get next character, don't bump * for (;;) * { start = out; 61$ move.l a3,a5 ; save current out address * opheader(); * unless (parse_pattern()) return FALSE; bsr opheader ; reserve space for opcode header bsr parse_pattern ; get sub-pattern beq.s 69$ ; if failed, then leave * patch_op(0, out, last_goto ? out - last_goto : 0); moveq #0,d0 ; size = 0 tst.l (sp) ; if last_goto is nonzero beq.s 62$ ; then size is still zero move.l a3,d0 ; size = out sub.l (sp),d0 ; size = out - last_goto 62$ move.l a5,a0 ; save start in a0 move.l a3,a5 ; write opcode to out, not start moveq #0,d1 ; opcode = 0 for now bsr patch_op ; patch in what we have move.l a0,a5 ; restore start ptr * last_goto = out; move.l a3,(sp) ; last_goto <-- out * opheader(); /* location of goto */ bsr opheader ; reserve space for opcode * if (*pat == ')') break; move.b (a2)+,d0 ; get next character cmp.b #')',d0 ; if close paren beq.s 63$ ; break loop * if (*pat != '|') return FALSE; cmp.b #'|',d0 ; if not OR bne.s 69$ ; goto failure * patch_op(PMATCH_CHOICE,start,out-start-2); move.l a3,d0 ; d0 <-- out sub.l a5,d0 ; d0 <-- out - start subq.l #2,d0 ; d0 <-- out - start - 2 moveq #PMATCH_CHOICE,d1 ; d1 = choice op bsr patch_op moveq #1,d3 ; IsWild = 1 bra.s 61$ ; do next part of group * pat++; * } * patch_op(PMATCH_NULL,start,out-start-2); 63$ move.l a3,d0 ; d0 <-- out sub.l a5,d0 ; d0 <-- out - start subq.l #2,d0 ; d0 <-- out - start - 2 moveq #PMATCH_NULL,d1 ; d1 = null op bsr patch_op * pat++; * for (;;) * { int offset; * offset = (last_goto[0]<< 8) + last_goto[1]; move.l (sp)+,a1 ; a1 <-- last_goto (also clean up stack) 64$ move.b (a1),d2 ; d2 <-- offset part 1 lsl.w #8,d2 ; shifted over 8 move.b 1(a1),d2 ; d2 <-- offset * patch_op(PMATCH_SKIP,last_goto,out-last_goto-2); move.l a1,a5 ; a3 <-- last_goto move.l a3,d0 ; d0 <-- out sub.l a1,d0 ; d0 <-- out - last_goto subq.l #2,d0 ; d0 <-- out - last_goto - 2 moveq #PMATCH_SKIP,d1 ; d1 = skip op bsr patch_op ; patch in opcode * if (offset == 0) break; * last_goto -= offset; tst.w d2 ; if last in chain beq endloop ; then parse next op sub.w d2,a1 ; last_goto -= offset bra.s 64$ ; loop 69$ addq #4,sp ; clean up stack bra parse_fail ;---------- parse "'" (tick) symbol * { if (*pat == TICK) /* skip over tick character */ * { pat++; * if (*pat=='\0') return FALSE; /* can't tick end of string */ * } * opdata(PMATCH_STRING); /* STRING match op */ * opdata(ToEnglish(*pat++)); /* character to match */ 70$ cmp.b #TICK,d0 ; if "'" character (tick) bne.s 75$ ; then do move.b (a2)+,d0 ; get next character beq parse_fail ; can't tick the end of string ;---------- parse normal character 75$ moveq #PMATCH_STRING,d1 ; put out a PMATCH_STRING opcode bsr opdata ; write to output buffer bsr ToEnglish ; put out normal character move.w d0,d1 ; d0 <-- data to write bsr opdata ; write character to output buffer endloop: tst.w d5 beq.s parse_succeed bra loop1 ; next character ;---------- finish up simple ops std_patch: bsr opheader ; reserve space for op header bsr patch_zeroop ; patch op with no data field moveq #1,d3 ; IsWild = 1 (wildcards present) tst.w d5 ; if ALL is true bne.s loop1 ; get next character ;---------- return success parse_succeed: move.l (sp)+,a5 ; restore starting point moveq #-1,d0 ; return failure code rts ; return ;---------- return failure parse_fail: move.l (sp)+,a5 ; restore starting point moveq #0,d0 ; return success code rts ; return ; register usage ; d0 - scratch ; d1 - current opcode ; d2 - length of op ; d4 - stack depth limit ; d5 - incomplete flag ; a0 - scratch ; a2 - name ; a3 - pattern ; a4 - pattern end xdef _PatternMatch,PatternMatch pmreg reg d2-d5/a2-a4 _PatternMatch: ; (pat, name) movem.l pmreg,-(sp) ; save regs move.l 28+4(sp),a3 ; get pat move.l 28+8(sp),a2 ; get name bra.s pm1 ; go to C entry point PatternMatch: ; (pat: a3, name:a2) movem.l pmreg,-(sp) ; save regs pm1: move.l sp,d4 ; d4 <-- stack pointer sub.l #1200,d4 ; d4 <-- lower limit of stack moveq #0,d5 ; set incomplete to FALSE move.l a3,a4 ; a4 <-- pat add.l #1000,a4 ; a4 <-- pat end (lots for now) bsr interpret_pattern ; call recursive match routine movem.l (sp)+,pmreg ; restore registers rts * int interpret_pattern(char *pat,int plength,int incomplete_ok) *{ char *save = name, * *save2; interpret_pattern: movem.l a3,-(sp) ; save pattern address on stack movem.l a2,-(sp) ; save name address on stack cmp.l sp,d4 ; compare stack ptr to stack limit bhs match_fail ; if d4 is higher, then stack too deep * if (plength == 0) return (*name == '\0'); cmp.l a3,a4 ; if we're at end of pattern bhi.s loop2 ; then tst.b (a2) ; if no more characters beq match_succeed ; then we succeeded bra match_fail ; else we failed * while (plength > 0) loop2: cmp.l a3,a4 ; while there's pattern left bls match_succeed * { WORD length, * code; * code = *pat & 0xf0; * length = ((pat[0] & 0x0f)<<8) + pat[1]; * plength -= 2; * pat += 2; move.b (a3)+,d1 ; get code byte move.b d1,d2 ; move to length and.w #$f,d2 ; extract length lsl.w #8,d2 ; times 256 move.b (a3)+,d2 ; get lower byte of length * switch (code) { lea jump_table(pc),a0 lsr.w #2,d1 and.w #$003c,d1 move.l (a0,d1.w),a0 jmp (a0) jump_table: dc.l match_eos ; 0x00 dc.l match_null ; 0x10 dc.l match_not ; 0x20 dc.l match_wild ; 0x30 dc.l match_pound ; 0x40 dc.l match_class ; 0x50 dc.l match_nclass ; 0x60 dc.l match_string ; 0x70 dc.l match_choice ; 0x80 dc.l match_skip ; 0x90 dc.l match_error ; 0xA0 dc.l match_error ; 0xB0 dc.l match_error ; 0xC0 dc.l match_error ; 0xD0 dc.l match_error ; 0xE0 dc.l match_error ; 0xF0 * case PMATCH_WILD: * if (*name == '\0') goto fail; * name++; * break; match_wild: tst.b (a2)+ ; can't wildcard end of string beq match_fail ; so that fails bra loop2 ; else it succeeds * case PMATCH_NULL: * break; match_null: bra loop2 ; do nothing at all * case PMATCH_EOS: * if (incomplete_ok || *name == '\0') return TRUE; * goto fail; match_eos: tst.w d5 ; if incomplete is OK bne match_succeed ; then we succeed tst.b (a2) ; if end of string beq match_succeed ; then we succeed bra match_fail ; else we fail * case PMATCH_NOT: * if (interpret_pattern(pat,plength,incomplete_ok) && *name == '\0') goto fail; * return TRUE; * break; match_not: bsr interpret_pattern ; call interpret_pattern beq match_succeed ; if test failed, then it succeeded tst.b (a2) ; if not end of string bne match_succeed ; then test also failed, but succeeded bra match_fail ; else we fail for real * case PMATCH_SKIP: * pat += length; * break; match_skip: add.w d2,a3 ; add length to pattern bra loop2 ; do next char * case PMATCH_CHOICE: * save2 = name; * if (interpret_pattern(pat,length + plength + 2,incomplete_ok)) return TRUE; * name = save2; * pat += length; * break; match_choice: add.w d2,a3 ; add length of op to pat move.l a3,-(sp) ; save next op addr on stack sub.w d2,a3 ; restore address to this op bsr interpret_pattern ; call interpret bne.s 10$ ; if succeeded, then ok move.l (sp)+,a3 ; restore next op addr from stack bra loop2 ; do next op 10$ addq #4,sp ; don't restore op addr from stack bra match_succeed ; and succeed * case PMATCH_NCLASS: * case PMATCH_CLASS: * plength -= length; * while (length--) * { if (length > 1 && pat[1] == '-') * { if (ToEnglish(*name) >= pat[0] && * ToEnglish(*name) <= pat[2]) * break; * else { pat += 3; length -= 2; } * } * else * { if (*pat == ToEnglish(*name)) break; * pat++; * } * } * pat += length + 1; * if (code == PMATCH_NCLASS) * { if (length >= 0) goto fail; * } * else * { if (length < 0) goto fail; * } * name++; match_class: match_nclass: move.b (a2),d0 ; get character in question jsr ToEnglish ; convert to UC english move.l a3,a1 ; a1 <-- pattern add.w d2,a1 ; a1 <-- next opcode (pattern + length) 20$ tst.w d2 ; check length beq.s 70$ ; if length is zero bmi.s 70$ ; or negative cmp.w #1,d2 ; if enough room for a range bls.s 50$ ; then see if there's a dash cmp.b #'-',1(a3) ; if it's a dash bne.s 50$ ; then check if character in range cmp.b 0(a3),d0 ; compare with first part of class blo.s 45$ ; if lower, then not in range cmp.b 2(a3),d0 ; compare with 2nd part of class bls.s 80$ ; if lower or same, then in class 45$ addq #3,a3 ; skip range definition subq #3,d2 ; subtract 3 from length bra.s 20$ ; check next member of class 50$ cmp.b (a3),d0 ; compare name byte with class byte beq.s 80$ ; if match, then go to "in class" 55$ addq #1,a3 ; next class character subq #1,d2 ; subtract 1 from length bra.s 20$ ; check next member of class ;---------- code to execute if character not in class 70$ cmp.b #PMATCH_CLASS/4,d1 ; if it's match class beq.s match_fail addq #1,a2 ; add 1 to name move.l a1,a3 ; next opode bra loop2 ;---------- code to execute if character in class 80$ cmp.b #PMATCH_NCLASS/4,d1 ; if it's match nclass beq.s match_fail addq #1,a2 ; add 1 to name move.l a1,a3 ; next opode bra loop2 * break; * case PMATCH_POUND: * for (;;) * { if (interpret_pattern(pat+length,plength-length,incomplete_ok)) return TRUE; * else if (!interpret_pattern(pat,length,TRUE)) goto fail; * } match_pound: move.w d2,-(sp) ; save length on stack add.w d2,a3 ; add op length to pat, giving op end bsr interpret_pattern ; interpret the pattern after this op bne.s 10$ ; if succeed, then return true move.w (sp),d2 ; get length of op again from stack movem.l d5/a4,-(sp) ; save pattern end and incomplete flg. move.l a3,a4 ; pattern end <-- pattern + pength sub.w d2,a3 ; pat <-- original pat moveq #-1,d5 ; set incomplete_ok to TRUE bsr interpret_pattern ; interpret op contents beq.s 20$ ; if no match then fail movem.l (sp)+,d5/a4 ; restore pattern end and incmplt. move.w (sp)+,d2 ; restore length from stack bra.s match_pound ; try another match. 10$ addq #2,sp ; clean up stack bra match_succeed ; and succeed 20$ lea 10(sp),sp ; clean up stack bra match_fail ; and fail * case PMATCH_STRING: * if (ToEnglish(*name++) != (length & 0x0ff)) goto fail; * break; match_string: move.b (a2)+,d0 ; get next character in name jsr ToEnglish ; convert to english upper case cmp.b d0,d2 ; if not the same as pat bne match_fail ; fail bra loop2 ; else next char * default: * Printf("Interpreter error!\n"); * return FALSE; match_error: bra.s match_fail ; just fail * return MATCH; match_succeed: addq #4,sp ; don't restore name move.l (sp)+,a3 ; restore pat address from stack moveq #-1,d0 ; return success rts *fail: * name = save; * return FALSE; match_fail: move.l (sp)+,a2 ; restore name address from stack move.l (sp)+,a3 ; restore pat address from stack moveq #0,d0 ; return failure rts